﻿//76.最小覆盖字串
class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = { 0 };
        int kinds = 0;
        for (int i = 0; i < t.size(); i++)
        {
            if (hash1[t[i]]++ == 0)
            {
                kinds++;
            }
        }

        string ans;

        int hash2[128] = { 0 };
        int len = INT_MAX, pos = 0;
        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            if (++hash2[s[right]] == hash1[s[right]])
            {
                count++;
            }

            while (count == kinds)
            {
                if (right - left + 1 < len)
                {
                    len = right - left + 1;
                    pos = left;
                }

                if (hash2[s[left]]-- == hash1[s[left]])
                {
                    count--;
                }
                left++;
            }
        }

        return len == INT_MAX ? "" : s.substr(pos, len);
    }
};